#include <cstdlib>
#include <iostream>
#include <map>
#include <fstream>
#include <iomanip>	//do setw
#include <vector>
#include <algorithm>
#include <string>
#include <ctime>
#define r 4
#define l 16
#define x 10
using namespace std;

struct Rozwiazanie
{

    int plansza[r][r];
    Rozwiazanie *poprzednie;
};

int zakonczenie[r][r];
vector < char > xx;
vector<string>kolejnosc_przeszukiwania;
vector<Rozwiazanie*>lista_rozwiazan;
vector<Rozwiazanie*>sciezka;

void wczytaj_plansze(vector<Rozwiazanie*>&lista_rozwiazan);
void wypisz_rozwiazanie(Rozwiazanie *do_wypisania);
bool sprawdz_czy_zakonczenie(Rozwiazanie *do_sprawdzenia);
void losowe_kierunki_wyszukiwania();
void utworz_stany_nastepne(vector<Rozwiazanie*>&nastepniki,Rozwiazanie *badane);
Rozwiazanie* nowe_rozwiazanie(Rozwiazanie *wzor);
bool sprawdz_czy_na_liscie(Rozwiazanie *sprawdzane);
bool DFS(Rozwiazanie *analizowany);
void BFS(Rozwiazanie* pierwsze);
void ukladanie_listy_drogi(Rozwiazanie* rozwiazanie_ostateczne);
void wypisz_sciezke();
////////////////////////////////////////////////////////////////////////////////
int main()
{


    int licznik=1;
    for (int i=0; i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            if (licznik<l)
            {
                zakonczenie[i][j]=licznik;
                licznik++;
            }
            else
            {
                zakonczenie[i][j]=0;
            }
        }
    }

    wczytaj_plansze(lista_rozwiazan);

    Rozwiazanie *wypisz;
    wypisz=lista_rozwiazan[0];
    wypisz_rozwiazanie(wypisz);		//wypisuje wczytana plansze z pliku

    losowe_kierunki_wyszukiwania();

    char wybor;
    cout<<endl<<"Wybierz algorytm przeszukiwania: "<<endl<<endl;
    cout<<"Rozwiazanie lamiglowki metoda DFS wybierz--> 'd' "<<endl;
    cout<<"Rozwiazanie lamiglowki metoda BFS wybierz--> 'b' "<<endl;
    cout<<endl;
    cout << "Wybor nalezy do Ciebie: ";
    cin >> wybor;
    cin.get();

    if (wybor=='d')
    {
        cout << endl <<"DFS"<< endl << endl;
        DFS(lista_rozwiazan[0]);
        ukladanie_listy_drogi(lista_rozwiazan[lista_rozwiazan.size()-1]);
    }
    else
    {
        if (wybor=='b')
        {
            cout << endl << "BFS"<< endl << endl;;
            BFS(lista_rozwiazan[0]);

        }
        else
        {
            cout << "Nieprawidlowy wybor."<<endl;
        }

    }
    wypisz_sciezke();

    return 0;
}

Rozwiazanie* nowe_rozwiazanie(Rozwiazanie *wzor)
{
    Rozwiazanie *nowe;
    nowe=new Rozwiazanie;

    for (int i=0; i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            nowe->plansza[i][j]=wzor->plansza[i][j];
        }
    }
    nowe->poprzednie=wzor;
    return nowe;
}
///////////////////////////////////////////////////////////////////////////////
void utworz_stany_nastepne(vector<Rozwiazanie*>&nastepniki,Rozwiazanie *badane)
{

    vector<Rozwiazanie*>lista_nastepnych;
    int w,k;
    for (int i=0; i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            if (badane->plansza[i][j]==0)
            {
                k=j;
                w=i;
            }
        }
    }
    Rozwiazanie *element;
    bool losowe=false;

    if (kolejnosc_przeszukiwania[0].compare("R")==0)
    {

        kolejnosc_przeszukiwania.erase(kolejnosc_przeszukiwania.begin(),kolejnosc_przeszukiwania.end());
        losowe=true;
        vector<string>temp_kolejnosc_poszukiwan;

        temp_kolejnosc_poszukiwan.push_back("L");


        temp_kolejnosc_poszukiwan.push_back("P");

        temp_kolejnosc_poszukiwan.push_back("G");

        temp_kolejnosc_poszukiwan.push_back("D");


        int losowanie;
        srand(time(NULL));
        for (int i=r; i!=0; i--)
        {

            losowanie=rand()%i;
            kolejnosc_przeszukiwania.push_back(temp_kolejnosc_poszukiwan[losowanie]);

            temp_kolejnosc_poszukiwan.erase(temp_kolejnosc_poszukiwan.begin()+losowanie);

        }

    }


    for (int z=0; z<kolejnosc_przeszukiwania.size(); z++)
    {


        if(kolejnosc_przeszukiwania[z].compare("G")==0)
        {
            if (w!=0)
            {
                element=nowe_rozwiazanie(badane);
                element->plansza[w][k]=badane->plansza[w-1][k];
                element->plansza[w-1][k]=0;
                lista_nastepnych.push_back(element);


            }
         }
         else
         {
            if(kolejnosc_przeszukiwania[z].compare("D")==0)
            {
                if(w!=3)
                {
                    element=nowe_rozwiazanie(badane);
                    element->plansza[w][k]=badane->plansza[w+1][k];
                    element->plansza[w+1][k]=0;
                    lista_nastepnych.push_back(element);

                }
            }
            else
            {
                if(kolejnosc_przeszukiwania[z].compare("L")==0)
                {
                    if (k!=0)
                    {
                        element=nowe_rozwiazanie(badane);
                        element->plansza[w][k]=badane->plansza[w][k-1];
                        element->plansza[w][k-1]=0;
                        lista_nastepnych.push_back(element);

                    }
                }
                else
                {
                    if(kolejnosc_przeszukiwania[z].compare("P")==0)
                    {
                        if (k!=3)
                        {
                            element=nowe_rozwiazanie(badane);
                            element->plansza[w][k]=badane->plansza[w][k+1];
                            element->plansza[w][k+1]=0;
                            lista_nastepnych.push_back(element);

                        }
                    }
                }
            }

        }
    }

    if(losowe==true)
    {
        kolejnosc_przeszukiwania.erase(kolejnosc_przeszukiwania.begin(),kolejnosc_przeszukiwania.end());
        kolejnosc_przeszukiwania.push_back("r");

    }

    nastepniki.swap(lista_nastepnych);
}
////////////////////////////////////////////////////////////////////////////////
bool sprawdz_czy_na_liscie(Rozwiazanie *sprawdzane)
{
    Rozwiazanie *porownywany;
    bool taki_sam=false;
    for (int i=0; i<lista_rozwiazan.size();i++)
    {
        if(taki_sam==true){return true;}
        else
        {
            taki_sam=true;
            porownywany=lista_rozwiazan[i];

            for (int j=0; j<r; j++)
            {
                for (int k=0; k<r; k++)
                {
                    if (sprawdzane->plansza[j][k]!=porownywany->plansza[j][k])
                    {
                        taki_sam=false;
                        break;
                    }
                }
            }
        }
    }
    return false;
}
////////////////////////////////////////////////////////////////////////////////
void BFS(Rozwiazanie* pierwsze)
{
    vector<Rozwiazanie*>rozwiazania_aktywne;
    vector<Rozwiazanie*>nastepniki;
    vector<Rozwiazanie*>temp_rozwiazania_aktywne;
    temp_rozwiazania_aktywne.push_back(pierwsze);


    bool rozwiazanie_znalezione=false;

    while(rozwiazanie_znalezione!=true)
    {
        rozwiazania_aktywne.swap(temp_rozwiazania_aktywne);
        temp_rozwiazania_aktywne.erase(temp_rozwiazania_aktywne.begin(),temp_rozwiazania_aktywne.end());
        nastepniki.push_back(rozwiazania_aktywne[0]);


        for (int i=0; i<rozwiazania_aktywne.size();i++)
        {

            utworz_stany_nastepne(nastepniki,rozwiazania_aktywne[i]);

            for (int j=0; j<nastepniki.size(); j++)
            {
                if(sprawdz_czy_na_liscie(nastepniki[j])==false)
                {
                    lista_rozwiazan.push_back(nastepniki[j]);

                    if (sprawdz_czy_zakonczenie(nastepniki[j])==true)
                    {


                        ukladanie_listy_drogi(nastepniki[j]);

                        rozwiazanie_znalezione=true;
                        break;
                    }
                    else
                    {
                        temp_rozwiazania_aktywne.push_back(nastepniki[j]);

                    }
                }

            }

            if(rozwiazanie_znalezione==true){break;}

        }
    }



}
////////////////////////////////////////////////////////////////////////////////
bool DFS(Rozwiazanie *analizowany)
{

    vector<Rozwiazanie*>stany_nastepne;
    utworz_stany_nastepne(stany_nastepne,analizowany);


    for (int i=0; i<stany_nastepne.size(); i++)
    {
        if(sprawdz_czy_zakonczenie(stany_nastepne[i])==true)
        {
            lista_rozwiazan.push_back(stany_nastepne[i]);

            return true;
        }
        else
        {
            if (sprawdz_czy_na_liscie(stany_nastepne[i])==false)
            {
                lista_rozwiazan.push_back(stany_nastepne[i]);
                if(DFS(stany_nastepne[i])==true)
                {

                    return true;
                }
            }
        }

    }
    return false;
}
////////////////////////////////////////////////////////////////////////////////
void losowe_kierunki_wyszukiwania()
{

    string tekst;
    tekst="P";
    kolejnosc_przeszukiwania.push_back(tekst);

}
////////////////////////////////////////////////////////////////////////////////
bool sprawdz_czy_zakonczenie(Rozwiazanie *do_sprawdzenia)
{
    for (int i=0;i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            if (do_sprawdzenia->plansza[i][j]!=zakonczenie[i][j])
            {
                return false;
                }
        }
    }
    return true;

}
////////////////////////////////////////////////////////////////////////////////
void wypisz_rozwiazanie(Rozwiazanie *do_wypisania)
{
    cout << endl << endl;
    for (int i=0; i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            cout <<setw(2)<< do_wypisania->plansza[i][j]<< " ";
        }
        cout << endl;
    }
}
////////////////////////////////////////////////////////////////////////////////
void wczytaj_plansze(vector<Rozwiazanie*>&lista_rozwiazan)
{
    vector<Rozwiazanie*>lista_do_eksportu;
    string plik="plik.txt";
   // cout<<"Wczytaj plansze do rozwiazania z pliku!"<<endl<<endl;
   // cout<<"Podaj nazwe pliku: ";
    //getline(cin,plik);

    Rozwiazanie *pierwsze;
    pierwsze=new Rozwiazanie;

    ifstream plik_dane (plik.c_str());

    for (int i=0; i<r; i++)
    {
        for (int j=0; j<r; j++)
        {
            plik_dane>>pierwsze->plansza[i][j];
        }
    }
    pierwsze->poprzednie=NULL;

    plik_dane.close();

    lista_do_eksportu.push_back(pierwsze);

    lista_rozwiazan.swap(lista_do_eksportu);
}
////////////////////////////////////////////////////////////////////////////////
void ukladanie_listy_drogi(Rozwiazanie* rozwiazanie_ostateczne)
{
    Rozwiazanie *poprzednik;
    sciezka.push_back(rozwiazanie_ostateczne);

    poprzednik=rozwiazanie_ostateczne;

    while(true)
    {
        if (poprzednik->poprzednie==NULL)
            {
            break;
            }
            poprzednik=poprzednik->poprzednie;
            sciezka.push_back(poprzednik);
    }
}
////////////////////////////////////////////////////////////////////////////////
void wypisz_sciezke()
{
        int licznik=-1;

        cout <<"Rozwiazanie lamiglowki:"<< endl;

    for (int i=sciezka.size()-1; i>=0; i--)
    {
        wypisz_rozwiazanie(sciezka[i]);

        licznik++;
    }
vector<char>::iterator it;
   for( it=xx.begin(); it!=xx.end(); ++it )
   {
     cout<< *it <<'\n';
   }


    cout<<endl;
    cout<<"Rozwialem lamiglowke w "<<licznik<<" przesunieciach"<<endl;
    cout << endl << "Wcisnij ENTER aby zakonczyc."<< endl;
    cin.get();
}
